package leetcode_core.leetcode_2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Subsets{

    private List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        backtrack(1,n,k,new LinkedList<>());
        return ans;
    }

    private void backtrack(int start, int n,int k,LinkedList<Integer> track){
        if(track.size() == k){
            ans.add(new ArrayList<>(track));
            return;
        }
        for(int i = start;i<=n;i++){
            //做选择
            track.add(i);
            //回溯递归
            backtrack(i+1,n,k,track);
            //撤销选择
            track.removeLast();
        }
    }


}
